/**
 * 哈希表
 * 基于数组实现，主要用于查找
 * 哈希表由哈希函数来确定每一个元素的存储位置。
 * 即：存储下标 = hashFun(存储元素, 存储表的最大长度)
 * 解决冲突的方法采用链地址法
 */

// 常量表
const MAX_LOAD_FACTOR = 0.75
const MIN_LOAD_FACTOR = 0.25

class HashMap {
    constructor(limit = 7) {
        // 存储容器
        this.storage = []
        // 存储总个数计数
        this.count = 0
        // 存储上限
        this.limit = limit
    }
    //内部哈希函数，传入数组项字符串，传入数组最大长度
    _hashFun(str, max) {
        // 采用霍纳算法建立下标与字符串的映射关系
        // 霍纳常数选取最好为质数
        // 初始化hashCode
        let hashCode = 0;
        for (let i = 0; i <= str.length - 1; i++) {
            //(((0*常数+字符1)*常数+字符2)*常数+字符3)*常数+字符4……
            hashCode = 31 * hashCode + str.charCodeAt(i)
        }
        //压缩，产生真正的下标值
        hashCode = hashCode % max
        return hashCode
    }
    //内部函数，判断一个数是否为质数
    _isPrime(num) {
        let num_sqrt = Math.ceil(Math.sqrt(num))
        for (let i = 2; i < num_sqrt; i++) {
            if (num_sqrt % i === 0) {
                return false
            }
        }
        return true
    }
    // 获得最近的质数
    _turnToPrime(num) {
        while (!this._isPrime(num)) {
            num++
        }
        return num
    }
    // 返回描述字符串
    toString() {
        let str = ""
        for (let index = 0; index <= this.storage.length - 1; index++) {
            str += `${index}号桶：`
            if (this.storage[index] === undefined || this.storage[index].length === 0) {
                str += "empty"
            } else {
                for (let j = 0; j <= this.storage[index].length - 1; j++) {
                    str += `(${this.storage[index][j].key} : ${this.storage[index][j].value}) -->`
                }
                str = str.slice(0, str.length - 3)
            }
            str += `\n`
        }
        return str
    }
    // 判空
    isEmpty() {
        return this.count === 0
    }
    //哈希表元素个数返回
    hashSize() {
        return this.count
    }
    // 置入/修改元素
    put({
        key,
        value
    }) {
        const index = this._hashFun(key, this.limit)
        //每个哈希表的位都是一个数组（或链表），得到这个数组（桶）
        let bucket = this.storage[index]
        //桶中无数据，初始化桶
        if (bucket === undefined) {
            bucket = []
            this.storage[index] = bucket
        }
        //判断是插入还是修改操作
        let overRide = false
        for (let i = 0; i <= bucket.length - 1; i++) {
            // 修改操作
            if (bucket[i].key === key) {
                bucket[i].value = value
                overRide = true
            }
        }
        //增加操作
        if (!overRide) {
            bucket.push({
                key,
                value
            })
            this.count++
            if (this.count > this.limit * MAX_LOAD_FACTOR) {
                this.resize(this._turnToPrime(this.limit * 2))
            }
        }
    }
    // 获取元素（查找）
    get(key) {
        //哈希函数根据key解析出对应的数组下标
        const index = this._hashFun(key, this.limit)
        //获取到相应的桶
        const bucket = this.storage[index]
        //如果不存在桶
        if (!bucket) {
            return null
        }
        for (let i = 0; i <= bucket.length - 1; i++) {
            if (bucket[i].key === key) {
                return bucket[i].value
            }
        }
        return null
    }
    // 删除元素
    delete(key) {
        const index = this._hashFun(key, this.limit)
        const bucket = this.storage[index]
        if (!bucket) {
            return null
        }
        for (let i = 0; i <= bucket.length - 1; i++) {
            if (bucket[i].key === key) {
                let value = bucket[i].value
                bucket.splice(i, 1)
                this.count--
                if (this.limit > 7 && this.count < this.limit * MIN_LOAD_FACTOR) {
                    this.resize(this._turnToPrime(Math.floor(this.limit / 2)))
                }
                return value
            }
        }
        return null
    }
    // 扩容
    resize(newLimit) {
        // 保存旧数据
        let oldStorage = this.storage
        // 重置属性
        this.storage = []
        this.count = 0
        this.limit = newLimit
        // 旧元素重新载入
        oldStorage.forEach(bucket => {
            if (bucket === undefined) {
                return
            }
            bucket.forEach(item => {
                this.put(item)
            })
        })
    }
}

module.exports = HashMap



// 测试用例
// const hm = new HashMap()
// hm.put({
//     key: 'jam',
//     value: 'thevalue'
// })
// hm.put({
//     key: 'age',
//     value: 18
// })
// hm.put({
//     key: 'job',
//     value: '6666666'
// })
// hm.put({
//     key: 'daddasdsada',
//     value: '6666666'
// })
// hm.put({
//     key: 'daddvasvada',
//     value: '888'
// })
// hm.put({
//     key: 'dadsgssada',
//     value: '888'
// })
// hm.put({
//     key: 'daddaefwfsdsada',
//     value: '888'
// })
// hm.put({
//     key: 'daddvrhwrsada',
//     value: '888'
// })
// hm.put({
//     key: 'dadhredbsada',
//     value: '888'
// })
// hm.put({
//     key: 'dadgsrada',
//     value: '888'
// })
// hm.put({
//     key: 'daddarw3rada',
//     value: '888'
// })
// hm.put({
//     key: 'daddasdsbdfbdada',
//     value: '888'
// })


// console.dir(hm.toString());